package com.tgy.programmer_code_interview_guide._02_linkedList;

/**
 * @Author: tgy
 * @Date: 1/25/21 9:24 AM
 */
public class _06_约瑟夫问题 {

    public static Node josephusProblem(Node node, int killNum) {

        if (node == null || node.next == null || killNum <= 0) {

            return node;
        }

        int num = 0;
        // 获取preNode节点
        Node preNode = node;
        while (preNode.next != node) {

            preNode = preNode.next;
        }

        while (true) {

            if (node.next == node) {

                break;
            }

            num++;

            if (num == killNum) {

                System.out.println(node.val);
                preNode.next = node.next;
                num = 0;
            }else {
                preNode = node;

            }
            node = node.next;
        }

        return node;
    }

      public static void main(String[] args) {

          Node root = new Node(1);
          root.next = new Node(2);
          root.next.next = new Node(3);
          root.next.next.next = new Node(4);
          root.next.next.next.next = new Node(5);
          root.next.next.next.next.next = root;

          System.out.println(josephusProblem(root, 3).val);
      }
}
